package Top_Interview_Questions_Review._011Heap;


import java.util.Comparator;
import java.util.PriorityQueue;

import Top_Interview_Questions_Review._005Divide_And_Conquer.Supple.ListNode;

/**
 * @Author: 吕庆龙
 * @Date: 2020/3/2 12:40
 * <p>
 * 功能描述:
 */
public class _0023 {

    public static void main(String[] args) {
        _0023 test = new _0023();
        ListNode[] listNodes = new ListNode[3];

        ListNode root1 = new ListNode(1);
        ListNode root1_node1 = new ListNode(4);
        ListNode root1_node2 = new ListNode(5);
        root1.next = root1_node1;
        root1_node1.next = root1_node2;

        ListNode root2 = new ListNode(1);
        ListNode root2_node1 = new ListNode(3);
        ListNode root2_node2 = new ListNode(4);
        root2.next = root2_node1;
        root2_node1.next = root2_node2;

        ListNode root3 = new ListNode(2);
        ListNode root3_node1 = new ListNode(6);
        root3.next = root3_node1;

        listNodes[0] = root1;
        listNodes[1] = root2;
        listNodes[2] = root3;

        System.out.println("主函数断点");

        test.mergeKLists(listNodes);


    }

    /*----------------------------------贪心算法+优先队列----------------------------------*/

    /**
     * https://leetcode-cn.com/problems/merge-k-sorted-lists/solution/leetcode-23-he-bing-kge-pai-xu-lian-biao-by-powcai/
     *
     * 1.时间复杂度：O(Nlogk)，这里 N 是这 k 个链表的结点总数，每一次从一个优先队列中
     * 选出一个最小结点的时间复杂度是 O(log k)，故时间复杂度为O(Nlogk)。
     * 2.空间复杂度：O(k)O(k)，使用优先队列需要 kk 个空间，“穿针引线”需要常数个空间，因此空间复杂度为
     * O(k)O(k)。
     *
     * 输入:
     * [
     *   1->4->5,
     *   1->3->4,
     *   2->6
     * ]
     * 输出: 1->1->2->3->4->4->5->6
     *
     */
    public ListNode mergeKLists1(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        PriorityQueue<ListNode> queue = new PriorityQueue<>(lists.length, new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                if (o1.val < o2.val) return -1;
                else if (o1.val == o2.val) return 0;
                else return 1;
            }
        });
        ListNode dummy = new ListNode(0);
        ListNode p = dummy;
        for (ListNode node : lists) {
            // 这一步很关键，不能也没有必要将空对象添加到优先队列中
            if (node != null)
                queue.add(node);
        }
        while (!queue.isEmpty()) {
            // 当前节点的 next 指针指向出队元素
            p.next = queue.poll();
            // 当前指针向前移动一个元素，指向了刚刚出队的那个元素
            p = p.next;
            // 只有非空节点才能加入到优先队列中
            if (p.next != null)
                queue.add(p.next);
        }
        return dummy.next;
    }

    /*-------------------------------------分治--------------------------------------------*/

    /**
     * 时间复杂度：O(Nlogk)，这里 N 是这 k 个链表的结点总数，k 个链表二分是对数级别的。
     * 空间复杂度：（待讨论）合并两个排序链表需要“穿针引线”的指针数为常数，主要的空间消耗在递归方法上。
     *
     */
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        return merge(lists, 0, lists.length - 1);
    }

    private ListNode merge(ListNode[] lists, int left, int right) {
        // 思考这里为什么取等于？这是因为根据下文对 mergeKLists 的递归调用情况，区间最窄的时候，
        // 只可能是左右端点重合
        if (left == right)
            return lists[left];
        int mid = left + (right - left) / 2;
        ListNode l1 = merge(lists, left, mid);
        ListNode l2 = merge(lists, mid + 1, right);
        return mergeTwoLists(l1, l2);
    }

    private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null)
            return l2;
        if (l2 == null)
            return l1;
        if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1,l2.next);
            return l2;
        }
    }

    /*---------------------------------------------------------------------------------*/

}
